#include <vector>
#include <string>
#include <queue>
#include <limits>
#include <set>

using namespace std;

class FordFulkerson
{
public:
    static int run(vector<vector<int>>& graph, int s, int t,
                   vector<bool>& path, int bricksNumber, string& result);
private:
    static bool findShortestPath(vector<vector<int>>& residualGraph,
                                 int s, int t, vector<int>& parent);
};

// находим кратчайший путь из s в t используя поиск в ширину
bool FordFulkerson::findShortestPath(vector<vector<int>>& residualGraph,
                                     int s, int t, vector<int>& parent)
{
	vector<bool> visited(parent.size());

	queue<int> q;
	q.push(s);
	visited[s] = true;
	parent[s] = -1;

	while (!q.empty())
    {
		int j = q.front();
		q.pop();

		for (int i = 0; i < residualGraph.size(); ++i)
        {
			if ((visited[i] == false) && (residualGraph[j][i] > 0))
			{
				q.push(i);
				parent[i] = j;
				visited[i] = true;

				if (i == t)
                {
					return true;
				}
			}
		}
	}
	return (visited[t] == true);
}

int FordFulkerson:: run(vector<vector<int>>& graph, int s, int t,
                        vector<bool>& path, int bricksNumber, string& result)
{
    // остаточный граф
    // сначала равен исходному
	vector<vector<int>> residualGraph(graph.size());
	for (int i = 0; i < graph.size(); ++i)
    {
		for (int j = 0; j < graph[i].size(); ++j)
		{
			residualGraph[i].push_back(graph[i][j]);
		}
	}

	vector<int> parent(graph.size());

	int maxFlow = 0;
	// пока есть путь из источника в сток по остаточному графу
	while (findShortestPath(residualGraph, s, t, parent))
    {
		int j;
		int pathFlow = numeric_limits<int>::max();
		for (int i = t; i != s; i = parent[i])
		{
			j = parent[i];
			path[j] = true;
			// определяем наибольшую мощность потока проходящего по остаточному графу
			pathFlow = min(pathFlow, residualGraph[j][i]);
		}
        // через все ребра в кратчайшем пути пустим pathFlow через остаточный граф
		for (int i = t; i != s; i = parent[i])
		{
			j = parent[i];
			residualGraph[i][j] += pathFlow;
			residualGraph[j][i] -= pathFlow;
		}

		maxFlow += pathFlow;
	}
	// восстанавливаем порядок кубиков, в котором они должны идти, чтобы получилось слово
	for (int i = bricksNumber + 1; i < residualGraph.size() - 1; ++i)
    {
        for (int j = 1; j <= bricksNumber; ++j)
        {
            if (residualGraph[j][i] != graph[j][i])
            {
                result.push_back(j + '0');
                result.push_back(' ');
            }
        }
    }
	return maxFlow;
}
